
#include <cstdlib>
#include <string>   // pour std::string
#include <fstream> 
#include <iostream>
#define ECART 1
#define PAS_DE_VOISIN -9998
#define EPSILON 0.001
#define debug 1

using namespace std;

enum type_ecoulement{
 inconnu,
 immobile 
};

/**
 * Créer une grille 
 * Attention a ne pas inverser les parametres
 */
   float ** allouerAltitudes(int _nrows, int _ncols){
      float ** altitudes;
	altitudes =new float*[_nrows]; // nb de ligne et donc taille d'une colonne
	for(int i= 0; i< _nrows ; i++){
	  altitudes[i] = new float[_ncols]; // allocation d'une ligne
	} 
    return altitudes;
    }
    
   void desallouerAltitudes(int _nrows, int _ncols,float ** _altitudes){
     for(int i=0;i<_nrows; i++){
      delete [] _altitudes[i]; 
     }
     delete [] _altitudes;
   }
   int ** allouerEcoulements(int _nrows, int _ncols){
      int ** ecoulements;
      ecoulements = new int * [_nrows]; // nb de ligne et donc taille d'une colonne
      for(int i= 0; i< _nrows ; i++){
	ecoulements[i] = new int[_ncols]; // allocation d'une ligne
      } 
    return ecoulements;
  }
    
   void desallouerEcoulements(int _nrows, int _ncols,int ** _ecoulements){
     for(int i=0;i<_nrows; i++){
      delete [] _ecoulements[i]; 
     }
     delete [] _ecoulements;
   }
    /**
     * Prendre une grille, créer une copie de la meme taille et copier les valeurs sur les bords
     */
     float ** copierBordsSeulement(int _nrows, int _ncols,float ** _altitudes){
      if(debug!=0){
	  cout<<"Debut copierBordsSeulement"<<endl;
      }
       float ** res= allouerAltitudes(_nrows,_ncols);
      //Copier la premiere colonne
      for(int row=0; row<_nrows ;row++){
	res[row][0]=_altitudes[row][0];
      }
      //Copier derniere colonne 
      for(int row=0; row<_nrows; row++){
	res[row][_ncols-1]=_altitudes[row][_ncols-1];
      }
      //Copier le morceau de la premiere ligne (pas la premiere case et pas la derniere)
      for(int col=1; col<_ncols-1; col++){
	res[0][col]=_altitudes[0][col];
      }
      //Copier le morceau de la derniere ligne (pas la premiere case et pas la derniere)
      for(int col=1; col<_ncols-1; col++){
	res[_nrows-1][col]=_altitudes[_nrows-1][col];
      }
      if(debug!=0){
	cout<<"fin de copieBords"<<endl;
      }
      return res;
    }

    
    /**
     * Prendre une grille, en faire une copie et retourner la copie
     */
  float ** creerCopieAltitudes(int _nrows, int _ncols, float ** _altitudes){
      float ** res= allouerAltitudes(_nrows,_ncols);
      for(int lig=0; lig<_nrows ;lig++){
	for(int col= 0; col < _ncols ; col++){
	  res[lig][col]=_altitudes[lig][col];
	}
    }
    return res;
  }
 /**
  * Afficher une grille
  */
 void afficherAltitudes(int _nrows, int _ncols, float ** _altitudes){ 
   if(debug!=0){
      cout<<"Afficher altitudes : "<<endl;
   }
   for(int i=0; i<_nrows; i++){
	for(int j=0; j<_ncols;j++){
	  cout<<"("<<i<<","<<j<<"): ";
	  cout<<"["<<_altitudes[i][j]<<"] ";
      }
      cout<<endl;
    }
  }
  void afficherEcoulements(int _nrows, int _ncols, int ** _ecoulements){ 
   if(debug!=0){
      cout<<"Afficher ecoulements : "<<endl;
   }
   for(int i=0; i<_nrows; i++){
	for(int j=0; j<_ncols;j++){
	  cout<<"("<<i<<","<<j<<"): ";
	  cout<<"["<<_ecoulements[i][j]<<"] ";
	}
      cout<<endl;
    }
  }
  /**
   * Trouver la valeur qui doit etre affectée a chaque case pour innonder la matrice
   */
  float valRemplissage(int _nrows, int _ncols,float ** _altitudes){
    if(debug!=0){ 
      cout<<"DEBUT de valRemplissage"<<endl;   
    }
    float altitudeMax=-9999;
      for(int i=0; i<_nrows; i++){
	for(int j=0; j<_ncols;j++){
	  if(_altitudes[i][j]>altitudeMax){
	    altitudeMax=_altitudes[i][j];
	  }
	}
      }
      if(debug!=0){
	cout<<"fin de valRemplissage"<<endl; 
     }
     return altitudeMax+ECART; //retourne la valuer max du MNT + un écart choisi
}
 
    /**
     * Prendre une grille, la copier, inonder la copie et retourner cette grille
     */
  float ** creerMatriceInnondee(int _nrows, int _ncols,float ** _altitudes){
    if(debug!=0){
      cout<<"Debut de creerMatriceInnondee"<<endl;  
    }
    float ** matriceInondee=copierBordsSeulement(_nrows,_ncols,_altitudes);
      //1 : trouver le max
      afficherAltitudes(_nrows,_ncols,matriceInondee);
      float maxAvecEcart=valRemplissage(_nrows,_ncols,_altitudes);
      for(int i=1; i<_nrows-1; i++){
	for(int j=1; j<_ncols-1;j++){
	  matriceInondee[i][j]=maxAvecEcart;
	}
      }
      if(debug!=0){
	cout<<"Fin de creerMatriceInnondee"<<endl;
      }
      return matriceInondee;
    }
  
  /**
   * Détermine si une case appartient a la grille, a partir de ses coordonnées
   * Par exemple sur une grille 4 par 4 :
   * (0,0) est sur la grille,
   * (4,3) n'est pas sur la grille
   * (-1,2) n'est pas sur la grille 
   */
  bool estSurGrille(int row, int col, int _nrows,int _ncols){
      if(row >= 0 && col >= 0 && row <= _nrows -1 && col <= _ncols-1) {
	 if(debug!=0){
	   cout<<row<<","<<col<<" sur la grille"<<endl;
	 }
	return true;
      } else {
	if(debug!=0){
	  cout<<row<<","<<col<<" PAS sur la grille"<<endl;
	}
	return false;
      }	
  }
  
   /**
   * Retourne un tableau contenant les altitudes des voisins
   * On retourne toujours un tableau de taille 8 dans cet ordre :
   * VoisinHautGauche, VoisinHaut, VoisinHautDroit, VoisinGauche, VoisinDroit, VoisinBasGauche, VoisinBas, VoisinBasDroit
   */
   float * altitudesVoisins(int row,int col,int _nrows, int _ncols, float ** altitudes){
    float * res= new float[8];
    for(int i=0; i<8; i++){
     res[i]=PAS_DE_VOISIN;
    }
    if(estSurGrille(row-1,col-1,_nrows,_ncols)){ // J'ai un voisin haut gauche
      res[0]=altitudes[row-1][col-1];
    }
    if(estSurGrille(row-1,col,_nrows,_ncols)){ // J'ai un voisin haut
      res[1]=altitudes[row-1][col];
    }
    if(estSurGrille(row-1,col+1,_nrows,_ncols)){ // J'ai un voisin haut droit
      res[2]=altitudes[row-1][col+1];
    }
    if(estSurGrille(row,col-1,_nrows,_ncols)){ // J'ai un voisin gauche
      res[3]=altitudes[row][col-1];
    }
    if(estSurGrille(row,col+1,_nrows,_ncols)){ // J'ai un voisin droit
      res[4]=altitudes[row][col+1];
    }
    if(estSurGrille(row+1,col-1,_nrows,_ncols)){ // J'ai un voisin bas gauche
      res[5]=altitudes[row+1][col-1];
    }
    if(estSurGrille(row+1,col,_nrows,_ncols)){ // J'ai un voisin bas
      res[6]=altitudes[row+1][col];
    }
    if(estSurGrille(row+1,col+1,_nrows,_ncols)){ // J'ai un voisin bas droit 
      res[7]=altitudes[row+1][col+1];
    }
    return res;
  }
  
  void afficheAltitudesVoisin(float * voisins){
    for(int i=0; i<8; i++){
      cout<<voisins[i]<<" ";
    }
    cout<<endl;
  }
    
    
  /**
   * Algorithme de remplissage des trous (Pseudo code donné dans le sujet)
   */
   void remplirTrous(int _nrows, int _ncols,float ** _altitudesZ,float **  _altitudesW){ 
    bool changement=true;
    while(changement){ 
      changement=false;
      for(int row=0; row<_nrows; row++){
	for(int col=0; col<_ncols; col++){ 
	  //cout<<"row,col : "<<row<<","<<col<<endl;
	  if(_altitudesW[row][col] > _altitudesZ[row][col]){
	    float * altVoisinsW = altitudesVoisins(row,col,_nrows,_ncols,_altitudesW);
	    //afficheAltitudesVoisin(altVoisinsW);
	    for(int v=0; v<8; v++){
	      if(altVoisinsW[v] != PAS_DE_VOISIN){ //Ce voisin est sur la grille, et son altitude est connue 
	      //cout<<"je suis sur le voisin "<<v<<" d'altitude "<<altVoisinsW[v]<<endl;
	      if(_altitudesZ[row][col] >= altVoisinsW[v]+EPSILON){ //condition 2
		_altitudesW[row][col]=_altitudesZ[row][col];
		  changement=true;
		}//fin condition 2
		else if(_altitudesW[row][col] > altVoisinsW[v]+EPSILON){ //condition 3
		  _altitudesW[row][col]=altVoisinsW[v]+EPSILON;
		  changement=true;
		}//fin condition 3   
	      }
	    }
	    delete [] altVoisinsW;
	  } //fin de condition 1
	}
      }  
    } //Fin du while
  }
  
 /**
  * Méthode permettant le calcul de l'ecoulement pour une case en particulier 
  * VoisinHautGauche 0,
  * VoisinHaut 1,
  * VoisinHautDroit 2,
  * VoisinGauche 3,
  * VoisinDroit 4,
  * VoisinBasGauche 5,
  * VoisinBas 6,
  * VoisinBasDroit 7
  * Immobile ecoulement.Immobile
  * Inconnu ecoulement.Inconnu
  */
  int calculUnEcoulementVersVoisins(int row, int col,int _nrows,int _ncols,float ** _altitudes,float _nodata_value){
    //Recuperer les altitudes des voisins
    float altitudeCourante=_altitudes[row][col];
    if(altitudeCourante==_nodata_value) return inconnu;
    else {
      float * altVoisins=altitudesVoisins(row,col,_nrows,_ncols,_altitudes);
      int indiceVoisinPLusPetiteAltitude=immobile; //initialisé a la valeur immobile
      bool minimumStrict=false;
      //Chercher d'abord un minimum strict c'est a dire une altitude plus basse
      for(int v=0; v<8; v++){ //Chercher le minimum (de 0 à 7)
	 if(altVoisins[v] != PAS_DE_VOISIN){
	  if(altVoisins[v] < altitudeCourante){
	      altitudeCourante=altVoisins[v];
	      indiceVoisinPLusPetiteAltitude=v; //si on trouve une altitude plus basse, on sauvegarde l'indice dans le tableau
	      minimumStrict=true;
	    }  
	  }
      }
      if(minimumStrict) return indiceVoisinPLusPetiteAltitude;
      else {
	//Si on a pas trouvé de minimum strict,
	//On cherche une altitude egale dans les voisins plus grand dans l'ordre lexicographique
	for(int v=0; v<4; v++){ 
	  if(altVoisins[v] == altitudeCourante){
	    return v;
	  } 
	}
	return 8;
      }
    }
  }
  
  /**
   * Pour chaque cellule, enregistrer la direction de l'ecoulement avec un entier
   */
  void calculerEcoulements(int _nrows,int _ncols,float ** _altitudes, int ** _ecoulements, float _nodata_value){
      for(int row=0; row<_nrows; row++){
	for(int col=0; col<_ncols; col++){ 
	  _ecoulements[row][col]=calculUnEcoulementVersVoisins(row,col,_nrows,_ncols,_altitudes,_nodata_value);
	}
      }
  }
  
  int * ecoulementsVoisin(){
    int * res= new int[8];
    /*
  for(int i=0; i<8; i++){
     res[i]=PAS_DE_VOISIN;
    }
    if(estSurGrille(row-1,col-1,_nrows,_ncols)){ // J'ai un voisin haut gauche
      res[0]=altitudes[row-1][col-1];
    }
    if(estSurGrille(row-1,col,_nrows,_ncols)){ // J'ai un voisin haut
      res[1]=altitudes[row-1][col];
    }
    if(estSurGrille(row-1,col+1,_nrows,_ncols)){ // J'ai un voisin haut droit
      res[2]=altitudes[row-1][col+1];
    }
    if(estSurGrille(row,col-1,_nrows,_ncols)){ // J'ai un voisin gauche
      res[3]=altitudes[row][col-1];
    }
    if(estSurGrille(row,col+1,_nrows,_ncols)){ // J'ai un voisin droit
      res[4]=altitudes[row][col+1];
    }
    if(estSurGrille(row+1,col-1,_nrows,_ncols)){ // J'ai un voisin bas gauche
      res[5]=altitudes[row+1][col-1];
    }
    if(estSurGrille(row+1,col,_nrows,_ncols)){ // J'ai un voisin bas
      res[6]=altitudes[row+1][col];
    }
    if(estSurGrille(row+1,col+1,_nrows,_ncols)){ // J'ai un voisin bas droit 
      res[7]=altitudes[row+1][col+1];
    }
    return res;
    */
    }
  
  //TODO
  //Renvoyer un tableau qui dit pour chaque voisin si ce voisin pointe vers la cellule dont on parle
  bool * pointeVersMoi(int row,int col, int _nrows, int _ncols, int ** _ecoulements){
   bool * res= new bool[8];
    /*
    
    //if(
    */
    return res;
  }
  //TODO
  /**
   * Méthode récursive qui va calculer le nombre de cellule qui pointent vers la cellule (row,col) en cours 
   */
  void calculFluxAccumulation(int row, int col,int _nrows,int _ncols,float ** _altitudes, int ** _ecoulements, int ** flux){
    
    
  }
  
  //TODO
  /**
   * Méthode qui va appeler calculFluxAccumulation sur les points de départs
   */
  void initCalculFlux(int _nrows,int _ncols,float ** _altitudes, int ** _ecoulements, int ** _flux){
    for(int row=0; row<_nrows; row++){
	for(int col=0; col<_ncols; col++){ 
	  if(_ecoulements[row][col]==immobile){
	    calculFluxAccumulation(row,col,_nrows,_ncols,_altitudes,_ecoulements,_flux);
	  }
	}
      }
  }
  
  
class mnt{
  private :
    int nrows;
    int ncols; 
    int xllcorner; 
    int yllcorner; 
    int cellsize;
    float nodata_value;
    float ** altitudes;
  public :
  mnt(int _nrows, int _ncols, int _xllcorner, int _yllcorner, int _cellsize, float _nodata_value, float ** _altitudes){
    nrows=_nrows;
    ncols=_ncols;
    xllcorner=_xllcorner;
    yllcorner=_yllcorner;
    cellsize=_cellsize;
    nodata_value=_nodata_value;
    altitudes=_altitudes;
  }
  /**
   * Constructeur de recopie
   * @param m : le mnt dont on veut une copie
   */
  mnt(const mnt & m){
   nrows=m.nrows;
   ncols=m.ncols;
   xllcorner=m.xllcorner;
   yllcorner=m.yllcorner; 
   cellsize=m.cellsize; 
   nodata_value=m.nodata_value;
   altitudes=creerCopieAltitudes(m.getNrows(),m.getNcols(),m.getAltitudes());
  }
  /**
   * Destructeur
   */
    ~mnt(){
      //Commencer par désallouer les colonnes
      for(int i=0; i<nrows; i++){
	if(altitudes[i]!=NULL){
	  delete[] altitudes[i];
	}
      }
    }
    int getNrows() const{
      return nrows;
    }

    int getNcols() const{
     return ncols; 
    }
    
    int getXllcorner() const{
     return xllcorner; 
    }
    
    int getYllcorner() const{
     return yllcorner; 
    }
    
    int getCellsize() const{
     return cellsize;
    }
    
    float getNodata_value() const{
     return nodata_value; 
    }
    
    float ** getAltitudes() const{
     return altitudes; 
    }
    
    void setNrows(int _nrows) {
      nrows=_nrows;
    }
    
    void setNcols(int _ncols) {
      ncols=_ncols;
    }
    
    void setXllcorner(int _xllcorner){
      xllcorner=_xllcorner;
    }
    
    void setYllcorner(int _yllcorner){
      yllcorner=_yllcorner; 
    }
    
    void setCellsize(int _cellsize){
      cellsize=_cellsize;
    }
    
    void setNodata_value(int _nodata_value){
     nodata_value=_nodata_value;
    }
    
    void setAltitudes(int _nrows, int _ncols, float ** _altitudes){
      altitudes=_altitudes;
    }
    void afficher(){
      cout<<"------- Mnt --------"<<endl;
      cout<<"nrows="<<nrows<<endl;
      cout<<"ncols="<<ncols<<endl;
      //cout<<"xllcorner="<<xllcorner<<endl;
      //cout<<"yllcorner="<<yllcorner<<endl;
      //cout<<"cellsize="<<cellsize<<endl;
      cout<<"nodata_value="<<nodata_value<<endl;
      afficherAltitudes(nrows,ncols,altitudes);
      cout<<"--------------------"<<endl;
    }
 
};
  
   mnt * lectureMnt(string nomFichier){
    ifstream file(nomFichier.c_str(), ios::in);
    if(file){
      string trash;
      int ncols, nrows, xllcorner, yllcorner, cellsize;
      float NODATA_value;
      float ** altitudes;
	file >> trash;
	  file >> ncols;
	  file >> trash;
	  file >> nrows;
	  file >> trash;
	  file >> xllcorner;
	  file >> trash;
	  file >> yllcorner;
	  file >> trash;
	  file >> cellsize;
	  file >> trash;
	  file >> NODATA_value;
	  altitudes = allouerAltitudes(nrows,ncols);
	  // on passe au remplissage du tableau
	  for(int lig=0; lig<nrows ;lig++){
	    for(int col= 0; col < ncols ; col++){
		file >> altitudes[lig][col];
	    }
	  }
      //mnt(int _nrows, int _ncols, int _xllcorner, int _yllcorner, int _cellsize, float _nodata_value, float ** _altitudes){
      return new mnt(nrows,ncols, xllcorner, yllcorner, cellsize,NODATA_value,altitudes);
   }
      else{
	cout<<"Impossible d'ouvrir le fichier '"<<nomFichier<<"'"<<endl;
	return NULL;
      }
      
  }
  
  int main(){
    mnt * m=lectureMnt("test_ecoulement.txt");
    //m->afficher();
   
    //cout<<"//////// Innondation /////"<<endl;
    //float ** matriceInondee=creerMatriceInnondee(m->getNrows(),m->getNcols(),m->getAltitudes());
    //afficherAltitudes(m->getNrows(),m->getNcols(),matriceInondee);
   
    /*
    float * altitudesVoisinsA=altitudesVoisins(nrows-1,ncols-1,nrows,ncols,m->getAltitudes(),m->getNodata_value());
    for(int i=0; i<8; i++){
     cout<<altitudesVoisinsA[i]<<" "; 
    }
    */
    //float ** bords= copierBordsSeulement(nrows,ncols,m->getAltitudes());
    //afficherAltitudes(nrows,ncols,bords);
    /**
     * Pour tester l'algo 1 :
     */
    /*
    float ** matriceInondee=creerMatriceInnondee(m->getNrows(),m->getNcols(),m->getAltitudes());
    afficherAltitudes(m->getNrows(),m->getNcols(),matriceInondee);
    remplirTrous(m->getNrows(),m->getNcols(),m->getAltitudes(),matriceInondee);
    afficherAltitudes(m->getNrows(),m->getNcols(),matriceInondee);
    */
    /**
     * Pour tester le calcul des ecoulements
     * 
     */
    int ** ecoulements = allouerEcoulements(m->getNrows(),m->getNcols());
    calculerEcoulements(m->getNrows(),m->getNcols(),m->getAltitudes(),ecoulements,m->getNodata_value());
    afficherEcoulements(m->getNrows(),m->getNcols(),ecoulements); 
    return 0;
  }
  //facade